#include "BTreeNode.h"

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf){
RC error;
error = (pf.read(pid, buffer));
if(error = 0){
	for(int i = 0;;i++){
		if(buffer[i].key != -1){
			keys[i] = buffer[i].key;
			rids[i] = buffer[i].rid;
		}
		else{
			nextPage = buffer[i].rid.pid;
			break;
		}
	}
}
return error;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
for(int i =0;i < ENTRIES_PER_NODE;i++){
	if(keys[i] == -1){
		buffer[i].rid.pid = nextPage;
		break;
	}
	buffer[i].rid = rids[i];
	buffer[i].key = keys[i];
	}
	return 0;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
int count = 0;
for(int i = 0;;i++){
	if(buffer[i].key != -1)
		count++;
	else
		break;
}

return count; 
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
int count = 0;
for(int a = 0; a < ENTRIES_PER_NODE; a++){
	if(keys[a] == -1)
		count++;
}
if(count == 0)
	return RC_NODE_FULL;
int hold;
int hold2;
RecordId hold3;
RecordId hold4;
for(int j = 0; j < ENTRIES_PER_NODE; j++){
	if(keys[j] > key || keys[j] == -1){
		hold = key;
		hold2 = keys[j];
		keys[j] = hold;
		hold = hold2;
		
		hold3 = rid;
		hold4 = rids[j];
		rids[j] = hold3;
		hold3 = hold4;
		
		for(int k = j+1;k < ENTRIES_PER_NODE-1;k++){
			hold2 = keys[k];
			keys[k] = hold;
			hold = hold2;
			
			hold4 = rids[k];
			rids[k] = hold3;
			hold3 = hold4;
		}
		break;
		}
}
return 0; }

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey){
							  
int keysPlus[ENTRIES_PER_NODE+1];
RecordId ridsPlus[ENTRIES_PER_NODE+1];
for(int i = 0; i < ENTRIES_PER_NODE;i++){
	keysPlus[i] = keys[i];
	ridsPlus[i] = rids[i];
}
	
int hold;
int hold2;
RecordId hold3;
RecordId hold4;
for(int j = 0; j < ENTRIES_PER_NODE+1; j++){
	if(keys[j] == -1){
		keys[j] = key;
		rids[j] = rid;
		break;
	}
	if(keys[j] > key){
		hold = key;
		hold2 = keysPlus[j];
		keysPlus[j] = hold;
		hold = hold2;
		
		hold3 = rid;
		hold4 = ridsPlus[j];
		ridsPlus[j] = hold3;
		hold3 = hold4;
		
		for(int k = j+1;k < ENTRIES_PER_NODE;k++){
			hold2 = keysPlus[k];
			keysPlus[k] = hold;
			hold = hold2;
			
			hold4 = ridsPlus[k];
			ridsPlus[k] = hold3;
			hold3 = hold4;
		}
		break;
		}
}
int firstNode = ((ENTRIES_PER_NODE+1)/2);
int secondNode = (ENTRIES_PER_NODE+1)-firstNode;

for(int m = 0; m < ENTRIES_PER_NODE; m++){
	if (m >= firstNode){
		keys[m] = -1;
	}
	else{
	keys[m] = keysPlus[m];
	rids[m] = ridsPlus[m];
	}
}	
for(int n = 0; n < secondNode; n++){
	sibling.keys[n] = keysPlus[n+firstNode];
	sibling.rids[n] = ridsPlus[n+firstNode];
} 
siblingKey = sibling.keys[0];
	
return 0; }

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
for(int i = 0; i < ENTRIES_PER_NODE;i++){
	if(keys[i] >= searchKey){
		eid = i;
		break;
	}
}
return 0; }

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
if(keys[eid] == -1 || eid > ENTRIES_PER_NODE)
	return RC_INVALID_ATTRIBUTE;
key = keys[eid];
rid = rids[eid]; 
return 0; }

/*
 * Return the pid of the next sibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
return nextPage;}

/*
 * Set the pid of the next sibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ nextPage = pid;
return 0; }

////////////////////////////////////NON_LEAF///////////////////////////////////////////////////////

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
RC error;
error = (pf.read(pid, buffer));
if(error = 0){
	for(int i = 0;;i++){
		if(buffer[i].key != -1){
			keys[i] = buffer[i].key;
			pids[i] = buffer[i].pid;
		}
		else{
			pids[i] = buffer[i].pid;
			break;
		}
	}
}
return error;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
for(int i = 0;i < PIDS_PER_NLNODE; i++){
	if(keys[i] == -1){
		buffer[i].pid = pids[i];
		break;
	}
	buffer[i].pid = pids[i];
	buffer[i].key = keys[i];
	}
	return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
int count = 0;
for(int i = 0;;i++){
	if(buffer[i].key != -1)
		count++;
	else
		break;
}

return count; 
} 


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
int count = 0;
for(int a = 0; a < KEYS_PER_NLNODE; a++){
	if(keys[a] == -1)
		count++;
}
if(count == 0)
	return RC_NODE_FULL;
int hold;
int hold2;
PageId hold3;
PageId hold4;
for(int j = 0; j < KEYS_PER_NLNODE; j++){
	if(keys[j] == -1){
		keys[j] = key;
		pids[j] = pid;
		break;
	}
	if(keys[j] > key){
		hold = key;
		hold2 = keys[j];
		keys[j] = hold;
		hold = hold2;
		
		hold3 = pid;
		hold4 = pids[j];
		pids[j] = hold3;
		hold3 = hold4;
		
		for(int k = j+1;k < KEYS_PER_NLNODE-1;k++){
			hold2 = keys[k];
			keys[k] = hold;
			hold = hold2;
			
			hold4 = pids[k];
			pids[k] = hold3;
			hold3 = hold4;
		}
		break;
		}
}
return 0; }

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
							  
int keysPlus[KEYS_PER_NLNODE+1];
PageId pidsPlus[PIDS_PER_NLNODE+1];
for(int i = 0; i < PIDS_PER_NLNODE;i++){
	keysPlus[i] = keys[i];
	pidsPlus[i] = pids[i];
}
int hold;
int hold2;
PageId hold3;
PageId hold4;
for(int j = 0; j < KEYS_PER_NLNODE+1; j++){
	if(keys[j] == -1){
		keys[j] = key;
		pids[j] = pid;
		break;
	}
	if(keys[j] > key){
		hold = key;
		hold2 = keys[j];
		keys[j] = hold;
		hold = hold2;
		
		hold3 = pid;
		hold4 = pids[j];
		pids[j] = hold3;
		hold3 = hold4;
		
		for(int k = j+1;k < KEYS_PER_NLNODE;k++){
			hold2 = keys[k];
			keys[k] = hold;
			hold = hold2;
			
			hold4 = pids[k];
			pids[k] = hold3;
			hold3 = hold4;
		}
		break;
		}
}
int firstNode = ((PIDS_PER_NLNODE+1)/2);
int secondNode = (PIDS_PER_NLNODE+1)-firstNode;

for(int m = 0; m < PIDS_PER_NLNODE; m++){
	if (m >= firstNode){
		keys[m] = -1;
	}
	else{
	keys[m] = keysPlus[m];
	pids[m] = pidsPlus[m];
	}
}	
for(int n = 0; n < secondNode; n++){
	sibling.keys[n] = keysPlus[n+firstNode];
	sibling.pids[n] = pidsPlus[n+firstNode];
} 
midKey = keys[firstNode-1];
	
return 0; }

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
for(int i = 0; i < KEYS_PER_NLNODE;i++){
	if(keys[i] > searchKey){
		pid = pids[i];
		break;
	}
	if(keys[i] == -1 || i == KEYS_PER_NLNODE-1){
		pid = pids[i+1];
		break;
	}
}
return 0; }

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{pids[0] = pid1;
pids[1] = pid2;
keys[0] = key; 
return 0; }
